package com.cat.binaryTree;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/split-linked-list-in-parts/
 * @create 2025/9/9 18:10
 * @since JDK17
 */

public class Solution04 {
    int len(ListNode head) {
        int n = 0;
        for (var p = head; p != null; p = p.next, n++);
        return n;
    }

    public ListNode[] splitListToParts(ListNode head, int k) {
        int n = len(head), m = n % k, len = n / k;   // 前m个可以多一个
        ListNode[] ans = new ListNode[k];
        ListNode p = head, q = head;
        for (int i = 1, j = 0; p != null; i = 1) {
            ans[j++] = p;
            while (p != null && (j <= m && i <= len) || (j > m && i < len)) {
                p = p.next;
                i++;
            }
            if (p == null) {
                break;
            }
            q = p;
            p = p.next;
            q.next = null;
        }

        return ans;
    }
}
